package tsp;

public class Dfs {
    public static int minCost = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int[][] nums = {{Integer.MAX_VALUE, 3, 6, 7, 5},
                {5, Integer.MAX_VALUE, 2, 3, 2},
                {6, 4, Integer.MAX_VALUE, 2, 3},
                {3, 7, 5, Integer.MAX_VALUE, 4},
                {5, 2, 3, 4, Integer.MAX_VALUE}
        };
        int len = nums.length;
        boolean visit[] = new boolean[len];
        Dfs dfs = new Dfs();
        dfs.dfs(nums, len, 0, 0, visit, 0, 0);
        System.out.println(minCost);
    }

    /**
     * 深度优先遍历获取最短路径
     * @param nums
     * @param len
     * @param y
     * @param start
     * @param visit
     * @param sum
     * @param count
     */
    public void dfs(int[][] nums, int len, int y, int start, boolean[] visit, int sum, int count) {
        if (count == len && y == start && sum < minCost) {
            minCost = sum;
        } else if (y == start && count > 0) {
            return;
        }

        for (int x = 0; x < len; x++) {
            if (!visit[x] && nums[y][x] != Integer.MAX_VALUE) {
                visit[x] = true;
                count++;
                sum += nums[y][x];
                dfs(nums, len, x, start, visit, sum, count);
                sum -= nums[y][x];
                count--;
                visit[x] = false;
            }
        }
    }
}
